import java.util.Arrays;

public class ZeroOnePack {
    private static final int N = 12;
    private static int[][] f = new int[N][N];
    private static int[] fPlus = new int[N];
    private static int[] weight = {0, 2, 2, 6, 5, 4};
    private static int[] v = {0, 6, 3, 5, 4, 6};
    private static int[] x = new int[N];

    public static int knap(int W, int n) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= W; j++) {
                if(j < weight[i]) {
                    f[i][j] = f[i - 1][j];
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - weight[i]] + v[i]);
                }
            }
        }
        /*for(int i = 1; i <= n; i++) {
            System.out.println(Arrays.toString(f[i]));
        }*/
        return f[n][W];
    }

    public static int knapPlus(int W, int n) {
        for(int i = 1; i <= n; i++) {
            for(int j = W; j >= weight[i]; j--) {
                fPlus[j] = Math.max(fPlus[j], fPlus[j - weight[i]] + v[i]);
            }
            //System.out.println(Arrays.toString(fPlus));
        }
        return fPlus[W];
    }

    public static int traceBack(int W, int n) {
        int r = W;
        int maxW = 0;
        for(int i = n; i > 0; i--) {
            if(f[i][r] != f[i - 1][r]) {
                x[i] = 1;
                maxW += weight[i];
                r = r - weight[i];
            } else {
                x[i] = 0;
            }
        }
        return maxW;
    }

    public static void display(int n) {
        System.out.println("最佳背包方案");
        for(int i = 0; i <= n; i++) {
            if(x[i] == 1) {
                System.out.printf("选取第%d种物品\n", i);
            }
        }
    }

    public static void main(String[] args) {
        int n = 5;
        int W = 10;
        System.out.println("重量：" + Arrays.toString(weight));
        System.out.println("价值：" + Arrays.toString(v));

        int maxV = knap(W, n);
        int maxVPlus = knapPlus(W, n);
        int maxW = traceBack(W, n);
        display(n);
        System.out.println("总价值：" + maxV + "  总重量：" + maxW);
        System.out.println("优化后总价值：" + maxVPlus);
    }
}
